package linkedlist.leetcode_147_medium_sort;

public class Debug {
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        insertionSortList(head);
    }
    public static ListNode insertionSortList(ListNode head) {
        //链表排序的经典base-case
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode lastSorted = head;
        ListNode cur = head.next;
        while (cur != null){
            //如果 < 待插入元素的值，说明这两个节点已经有序，继续遍历
            if(lastSorted.val <= cur.val){
                lastSorted = cur;
                cur = cur.next;
            }else { //cur的值更小，插入到合适的位置。
                ListNode pre = dummyNode;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                lastSorted.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;

                //下一个待插入元素
                cur = lastSorted.next;
            }
        }
        return dummyNode.next;
    }
}
